// https://leetcode.cn/problems/missing-two-lcci/

// 题干：给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。
//       你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
//       以任意顺序返回这两个数字均可。

// 示例：输入: [1]
//       输出: [2,3]

// 碎语：本题难度为hard，实际上只要分步破解就还行
//       一步一步要有逻辑即可
//       第一步先异或数组的所有数字，再异或[1,N]的所有数字，结果是所缺少的两个数字的异或
//       利用分组思想，要把这两个数字给分开
//       我们找到异或结果最后的一个数字1，这就是两个缺少数字的不同的地方，可以成为我们的分组依据


#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    vector<int> missintTwo(vector<int>& nums)
    {
        // 先求出两个缺少数字异或的结果
        int inf = 0;
        for (int i = 0 ; i < nums.size() ; i++){
            inf ^= nums[i];
        }
        for (int i = 1 ; i <= nums.size() + 2 ; i++){
            inf ^= i;
        }
        inf = inf & (-inf); // 提取异或和的最后一位1

        //  借助分界点分组异或
        int retA = 0, retB = 0;
        for (int i = 0 ; i < nums.size() ; i++){
            if (nums[i] & inf) retA ^= nums[i];
            else retB ^= nums[i];
        }
        for (int i = 1 ; i <= nums.size() + 2 ; i++){
            if (i & inf) retA ^= i;
            else retB ^= i;
        }

        return {retA, retB};
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {1};

    vector<int> index = sol.missintTwo(nums);
    for (const int& num : index){
        cout << num << " ";
    }
    cout << endl;

    return 0;
}